package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class SubstringwithConcatenationofAllWords
{

  //pass both O(NL)
  public static ArrayList<Integer> findSubstring1(String S, String[] L) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<Integer> ans = new ArrayList<Integer>();
    HashMap<String, Integer> count = new HashMap<String, Integer>();
    HashMap<String, Integer> found = new HashMap<String, Integer>();
    for(String l : L){
      if (count.get(l) == null) count.put(l, 1);
      else count.put(l, count.get(l) + 1);
    }
    int l = L[0].length();
    int n = L.length;
    loop : for(int i = 0; i < S.length() - l * n + 1 ; i++){
      String sub = S.substring(i, i + l);
      // if L has this sub
      if(count.get(sub) != null){
        found.clear();
        found.put(sub, 1);
        //if i is the answer
        //then i + n * L should contain all L
        for(int j = 1 ; j < n; j++){
          int s = i + j * l;
          sub = S.substring(s, s + l);
          
          if (found.get(sub) == null) found.put(sub, 1);
          else found.put(sub, found.get(sub) + 1);
          
          Integer toFind = count.get(sub);
          if (toFind == null) continue loop;
          
          Integer foundVal = found.get(sub);
          
          if (foundVal > toFind) continue loop;
          found.put(sub, foundVal);
        }
        ans.add(i);
      }
        
      
      
    }
    return ans;
  }
  
  
  
  //there exist linear algorithm
  
  
  
  //pass both take longer time?
  public static ArrayList<Integer> findSubstring(String S, String[] L) {
    // Start typing your Java solution below
    // DO NOT write main() function

    ArrayList<Integer> ret = new ArrayList<Integer>();
    if (L.length == 0) {
        return ret;
    }

    //I will create another string array without the duplcates
    ArrayList<String> l = new ArrayList<String>();
    ArrayList<Integer> c = new ArrayList<Integer>();

    Arrays.sort(L);
    for (int i = 0; i < L.length; i++) {
        l.add(L[i]);
        int count = 1;
        while (i+1 < L.length && L[i].equals(L[i+1])) {
            i++;
            count++;
        }
        c.add(count);
    }

    int[] starts = new int[S.length()];


    for (int i = 0; i < S.length(); i++) {
        starts[i] = -1;
        for (int j = 0; j < l.size(); j++) {
            if (S.substring(i).startsWith(l.get(j))) {
                starts[i] = j;
            }
        }
    }

    int step = L[0].length();

    for (int i = 0; i <= S.length() - step*L.length; i++) {
        int[] perm = new int[L.length];
        boolean needTest = true;
        for (int j = 0; j < L.length; j++) {
            perm[j] = starts[i+j*step];
            if (perm[j] == -1) {
                needTest = false;
            }
        }   
        if (needTest && testPerm(perm, c)) {
            ret.add(i);
        }
    }

    return ret;
}

private static boolean testPerm (int[] perm, ArrayList<Integer> c) {
    int[] count = new int[c.size()];
    for (int i = 0; i < count.length; i++) {
        count[i] = 0;
    }

    for (int i = 0; i < perm.length; i++) {
        count[perm[i]]++;
    }

    for (int i = 0; i < count.length; i++) {
        if (count[i] != c.get(i)) {
            return false;
        }
    }

    return true;
}
  
  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    String s = "abaababbaba";
    String[] L = {"ba","ab","ab"};
    findSubstring(s,L);
  }

}
